package xin.luna.exercise;

import xin.luna.structs.StackLinkedTable;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

/**
 * Chapter 1 Section 3 Exercise 9: 编写一段程序，从标准输入得到一个缺少左括号的表达式并打印出不全括号之后的中序表达式。例如，给定输入：1 + 2 ) * 3 - 4
 * ) * 5 - 6 ) ) ) 应该输出：( ( 1 + 2 ) * ( ( 3 - 4 ) * ( 5 - 6 ) ) )
 */
public class C1S3E9 {
  public static void main(String[] args) {
    StackLinkedTable<String> stack = new StackLinkedTable<>();

    while (!StdIn.isEmpty()) {
      String item = StdIn.readString();
      if (!item.equals(")")) {
        stack.push(item);
      } else {
        StringBuilder sb = new StringBuilder(item);

        int counter = 0;
        while (true) {
          if (stack.isEmpty()) {
            break;
          }

          if (counter <= 2) {
            sb.insert(0, stack.pop());
          } else {
            break;
          }
          counter++;
        }

        sb.insert(0, "(");
        stack.push(sb.toString());
      }
    }

    for (String item : stack) {
      StdOut.println(item);
    }
  }
}
